#include "grafo.h"
#include "common.h"

#include <cstdlib>
#include <iostream>
#include <algorithm>

/*======================================================================
	Algoritmo goloso constructivo
------------------------------------------------------------------------
======================================================================*/
using namespace std;

//Obtener que nodos serian dominados si agregaramos el nodo pasado
//por parametro al conjunto dominante
static inline int queDominaria(const Grafo & grafo, 
			const vint & dominado, int nodo){

	const vint & vecino = grafo.vecinos(nodo);
	int vecinos = vecino.size(), dominaria = 0;

	if(!dominado[nodo]) dominaria++;
	for(int j = 0; j < vecinos; j++){
		if(!dominado[vecino[j]]) 
			dominaria++;
	}
	return dominaria;
}

//Marcar el nodo como un nodo dentro del conjunto dominante.
static inline int marcar(const Grafo & grafo, vint & dominado, 
			vint & dominante, int maximoNodo){
	
	int nuevos = 0;
	if(!dominado[maximoNodo]){
		nuevos++;
	}
	
	dominante[maximoNodo] = dominado[maximoNodo] = true;
	const vint & vecino = grafo.vecinos(maximoNodo);
	int vecinos = vecino.size();
	
	for(int i = 0; i < vecinos; i++){
		int nodo = vecino[i];
		if(!dominado[nodo]){ 
			nuevos++;
			dominado[nodo] = true;
		}
	}
	return nuevos;
}

//Devuelve los nodos marcados como "dominantes" de la componente
//Le pasamos la cantidad de dominantes para que pueda
//reservar ese espacio y no tengamos tanto overhead.
static inline vint dominantes(const vint & componente,
			const vint & dominante, int total){
	
	int nodosComponente = componente.size();
	vint resultado(total); int ind = 0;
	for(int i = 0; i < nodosComponente; i++){
		int nodo = componente[i];
		if(dominante[nodo]){
			resultado[ind++] = nodo;
		}
	}
	
	return resultado;
}

//Algoritmo goloso constructivo (Ejercicio 2)
vint goloso(const Grafo & grafo, const vint & componente){
	int nodosComponente = componente.size(), total = 0, enDominante = 0;

	vint dominado(grafo.nodos(),false), 
	     dominante(grafo.nodos(),false);
	     		
	while(total < nodosComponente){
		int maximo = 0, maximoNodo = -1;
		for(int i = 0; i < nodosComponente; i++){
			int nodo = componente[i];			
			if(dominante[nodo]) continue;
			
			int dominaria = queDominaria(grafo,dominado,nodo);
			if(dominaria > maximo){
				
				maximo = dominaria;
				maximoNodo = nodo;
			}
		}
					
		total += marcar(grafo,dominado,dominante,maximoNodo);
		enDominante++;
	}
	
	return dominantes(componente,dominante,enDominante);
}

//Algoritmo goloso constructivo randomizado, usando como primer
//paso de la metaheuristica GRASP
vint golosoRandom(const Grafo & grafo, const vint & componente, 
			int porcentaje, int semilla){

	assert(porcentaje > 0 && porcentaje <= 100);

	int nodosComponente = componente.size(), total = 0, enDominante = 0;	
	vint dominado(grafo.nodos(),false), 
	     dominante(grafo.nodos(),false);
	
	while(total < nodosComponente){
		//Poner los nodos en una cola de prioridad
		//La razon por la cual se toman pares es porque en la STL
		//pair tiene orden por primera coordenada.
		std::vector< pair<int,int> >
			ordenamiento(nodosComponente-enDominante);
		
		int ind = 0;
		for(int i = 0; i < nodosComponente; i++){
			int nodo = componente[i];	
			if(dominante[nodo]) continue;
			
			ordenamiento[ind++] = 
				make_pair(queDominaria(grafo,dominado,nodo),nodo);
		}

		make_heap(ordenamiento.begin(),ordenamiento.end());
		int nodosCandidatos = ordenamiento.size();

		//Tomar los porcentaje primeros y de esos elegir uno al azar.
		int sacar = max(1,(porcentaje*nodosCandidatos)/100), candidato;
				
		while(sacar-- > 0){
			candidato = ordenamiento.front().second;
			pop_heap(ordenamiento.begin(),ordenamiento.end());
		}
		total += marcar(grafo,dominado,dominante,candidato);
		enDominante++;
	}
	
	return dominantes(componente,dominante,enDominante);
}
